#pragma once
#include<iostream>
#include<string>
#include<vector>
#include<cassert>

using namespace std;
namespace zxj
{
	template<class T>
	struct listNode
	{
		T _data = T();
		listNode<T>* _next =nullptr;
		listNode<T>* _prev = nullptr;

		listNode(const T& data = T())
			:_data(data)
		{
		}
	};

	template<class T,class Ref,class Ptr>
	struct iteratorList
	{
	public:
		using self = iteratorList<T, Ref, Ptr>;
		using pnode = listNode<T>;
	public:
		iteratorList(pnode* node)
			:_node(node)
		{}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &operator*();
		}

		bool operator!=(const self& it)
		{
			return _node != it._node;
		}

	public:
		pnode* _node = nullptr;
	};
	
	template<class T>
	class list
	{
	public:
		using node = listNode<T>;
		using iterator = iteratorList<T, T&, T*>;
		using const_iterator = iteratorList<T, const T&, const T*>;
	public:
		list()
		{
			initEmpty();
		}

		list(int  n, const T& val = T())
		{
			initEmpty();
			for (int i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}
		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			initEmpty();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list(const list<T>& x)
		{
			initEmpty();
			list<T> tmp(x.begin(), x.end());
			swap(tmp);
		}

		list<T>& operator=(list<T> x)
		{
			swap(x);
			return *this;
		}

		~list()
		{
			clear();
			destory();
		}

		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}


		const_iterator begin() const
		{
			return iterator(_head->_next);
		}

		const_iterator end() const
		{
			return iterator(_head);
		}

		void push_back(const T& data)
		{
			//node* newnode = new node(data);
			//node* tail = _head->_prev;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//tail->_next = newnode;
			//_head->_prev = newnode;
			insert(end(), data);
		}
		void push_front(const T& data)
		{
			insert(begin(), data);
		}

		void pop_back()
		{
			//assert(!empty());
			//node* p = _head->_prev;
			//node* tail = p->_prev;
			//_head->_prev = tail;
			//tail->_next = _head;
			//delete p;
			erase(--end());
		}
		void pop_front()
		{
			erase(begin());
		}


		bool empty()const
		{
			return _head == _head->_next;
		}


		void clear()
		{
			node* p = _head->_next;
			while (p!=_head)
			{
				node* next = p->_next;
				delete p;
				p = next;
			}
			_head->_next = _head;
			_head->_prev = _head;
		}

		iterator insert(iterator pos, const T& data)
		{
			node* cur = pos._node;
			node* prev = cur->_prev;
			node* newnode = new node(data);
			newnode->_next = cur;
			newnode->_prev = prev;
			cur->_prev = newnode;
			prev->_next = newnode;
			return pos;
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());
			assert(!empty());
			node* cur = pos._node;
			node* prev = cur->_prev;
			node* next = cur->_next;
			next->_prev = prev;
			prev->_next = next;
			delete cur;
			return iterator(next);
		}

		void swap(list<T>& x)
		{
			std::swap(_head, x._head);
		}

		void debugPrint() const
		{
			node* p = _head->_next;
			while (p != _head)
			{
				node* next = p->_next;
				cout << p->_data << " ";
				p = next;
			}
			cout << endl;
		}

	private:
		void initEmpty()
		{
			_head = new node();
			_head->_next = _head;
			_head->_prev = _head;
		}

		void destory()
		{
			delete _head;
			_head = nullptr;
		}


	private:
		node* _head;
	};

	void TestList1()
	{
		int a[] = { 1,2,3,4,5,6,7,8,9 };
		list<int> l1;
		for (const auto& e : a)
		{
			l1.push_back(e);
		}
		l1.debugPrint();
		l1.pop_back();
		l1.debugPrint();
		l1.pop_back();
		l1.debugPrint();
		l1.pop_back();
		l1.debugPrint();
		l1.pop_back();
		l1.debugPrint();
		l1.pop_back();
		l1.debugPrint();
		l1.pop_back();
		l1.debugPrint();
		l1.pop_back();
		l1.debugPrint();
		//l1.pop_back();
		//l1.debugPrint();
		//l1.pop_back();
		//l1.debugPrint();
		//l1.pop_back();
		//l1.debugPrint();
	}

	void TestList2()
	{
		int a[] = { 1,2,3,4,5,6,7,8,9 };
		list<int> l1;
		for (const auto& e : a)
		{
			l1.push_back(e);
		}

		for (const auto& e : l1)
		{
			cout << e << " ";
		}
		cout << endl;
	}
	void TestList3()
	{
		int a[] = { 1,2,3,4,5,6,7,8,9 };
		list<int> l1;
		for (const auto& e : a)
		{
			l1.push_back(e);
		}
		l1.erase(++++++l1.begin());
		l1.debugPrint();
	}
}